home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 1442 < prev    next >
Encoding:
Text File  |  1996-08-05  |  4.5 KB  |  115 lines
  1. Path: news.iag.net!news
  2. From: jatmon@iag.net (John R Buchan)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: a tree problem. Complex or not ? is it a classic problem ?
  5. Date: 14 Jan 1996 01:03:11 GMT
  6. Organization: Internet Access Group, Orlando, Florida
  7. Message-ID: <4d9kof$44r@news.iag.net>
  8. References: <4d60ln$nac@hermes.fundp.ac.be>
  9. NNTP-Posting-Host: pm4-orl3.iag.net
  10. X-Newsreader: WinVN 0.99.7
  11.  
  12. In article <4d60ln$nac@hermes.fundp.ac.be>, fmelo@biq.fundp.ac.be says...
  13. >
  14. >Hi Everybody !, I have a complex tree constructed with this structure:
  15. >
  16. >struct heavy_atom
  17. >{
  18. >        int atom_number;             /* Atom serial number */
  19. >        char atom_name [8];          /* Atom name */
  20. >        char res_name_3 [8];         /* 3 letters residue name */
  21. >        char res_name_1;             /* 1 letter residue name */
  22. >        char chain [8];              /* Chain identifier */
  23. >        int res_number;              /* Residue sequence number */
  24. >        float x;                     /* Orthogonal coordinate for X */
  25. >        float y;                     /* Orthogonal coordinate for Y */
  26. >        float z;                     /* Orthogonal coordinate for Z */
  27. >        float occ;                   /* Occupancy */
  28. >        float temp_f;                /* Temperature factor */
  29. >        int atom_type;               /* atom type (user definition) */
  30. >       struct heavy_atom *prev_ptr;  /* Pointer to previous heavy_atom */
  31. >       struct heavy_atom *next_ptr;  /* Pointer to next heavy_atom */
  32. >       struct heavy_atom *ca_ptr;    /* Pointer alpha carbon direction */
  33. >       struct heavy_atom *nh2_ptr;   /* Pointer in NH2 direction */
  34. >       struct heavy_atom *cooh_ptr;  /* Pointer in COOH direction */     
  35. >       struct heavy_atom *r1_ptr;    /* Pointer in R1 direction */
  36. >       struct heavy_atom *r2_ptr;    /* Pointer in R2 direction */
  37. >       struct heavy_atom *r3_ptr;    /* Pointer in R3 direction */
  38. >};
  39. >
  40. >Despite of this structure appears like a multidimensional tree with 8 
  41. >potential pointers to another elements, it is not. It is only a 
  42. >tridimensional tree because some pointers will point to NULL. I am using 
  43. >this structure in the way of represent in memory the "real structure" of 
  44. >a molecule (a protein in this case). Every node in the tree represents an 
  45. >atom with all these data and with the pointers that will give the 
  46. >connectivity of each atom with the other ones. Because the maximum 
  47. >connectivity of each atom is 4 (for a carbon atom) this tree will be only 
  48. >tridimensional.
  49. >
  50. >After this "short" (some people will find it very long) introduction I 
  51. >will tell my problem. 
  52. >
  53. >If I am in a node (some atom, doesn't matter which one) and if I define 
  54. >the distance between to nodes as "1", I would like to have an algorithm 
  55. >(or strategy) for identify all the nodes (or atoms) which its distance to 
  56. >the current node is i.e "16". Does exist a strategy or an algorithm for 
  57. >do this ???, is it a classic problem with trees ???.
  58.  
  59. If I understand you request, something like the following, might fit the
  60. bill.  I haven't tested it (I'm too lazy to write the code to generate a
  61. molecule to test it on :-) ), but I'm sure that someone in the group will
  62. point out any glaring errors I missed.  It can be rewritten to avoid the 
  63. dist'nth round of recursions.
  64.  
  65. int CountNodesAtDistance( struct heavy_atom *thisNode, int dist)
  66.    {
  67.    static int currDist = 0;
  68.    int count = 0;
  69.    
  70.    if( dist <= 0)    /* just a sefety */
  71.       return 0;
  72.                           
  73.    if( currDist == dist)  /* node at correct distance, count it */
  74.       count = 1; 
  75.    else                  /* check the next layer out */
  76.       {
  77.       currDist++; 
  78.       
  79.       if( thisNode->prev_ptr != NULL)   
  80.          count += CountNodesAtDistance( thisNode->prev_ptr, dist);
  81.    
  82.       if( thisNode->next_ptr != NULL)   
  83.          count += CountNodesAtDistance( thisNode->next_ptr, dist);
  84.    
  85.       if( thisNode->ca_ptr != NULL)   
  86.          count += CountNodesAtDistance( thisNode->ca_ptr, dist);
  87.    
  88.       if( thisNode->nh2_ptr != NULL)   
  89.          count += CountNodesAtDistance( thisNode->nh2_ptr, dist);
  90.       
  91.       /* etc. */ 
  92.    
  93.       currDist--;
  94.       }
  95.    
  96.    return count;
  97.    }
  98.    
  99.  
  100. int main(void)
  101.    {
  102.    struct heavy_atom *base;
  103.                                    
  104.    /* of course, you'd nave to created your molecule, so that base is valid */                                   
  105.    CountNodesAtDistance( base, 16);
  106.  
  107.    return (0);
  108.    }
  109.  
  110.  
  111. -- 
  112. John R Buchan           -:|:-     Looking for that elusive FAQ?  ftp to:
  113. jatmon@mail.iag.net     -:|:-     rtfm.mit.edu /pub/usenet-by-group/....
  114.  
  115.